'''
https://leetcode.cn/problems/sqrtx/description/?envType=study-plan-v2&envId=top-interview-150
'''
import math

epsilon = 1e-5
class Solution:

    # 利用e，转换为指数，对数，公式
    # y = x^(1/2) , x = e^(lnx)
    #   y=(e^(lnx))^(1/2) = e^(1/2(lnx))
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        res = math.exp(0.5 * math.log(x))
        res = int(res)   # notice: 近似计算，这个取整是向下的，有可能是向上一个才是对的
        if (res + 1) * (res + 1) <= x:
            return res + 1
        return res

    # 设 f(x) = x^2 - c, 当x=根号c，时f(x) = 0
    # 牛顿迭代法, f(x+deltax) 约等 f(x) + f'(x)deltax
    #                           => f(xk) = -f'(xk)deltax
    #                           => deltax = -f(xk)/f'(xk)       deltax = x{k+1} - xk
    # x{k+1} = xk-f(xk)/f'(xk)
    def mySqrt2(self, C: int) -> int:
        if C == 0: return 0

        def f(x):
            return x * x - C
        def f_derivative(x):
            return 2 * x
        x = C
        while f(x) >= epsilon or f(x) <= -epsilon:
            x = x - f(x)/f_derivative(x)
        return int(x)
    def mySqrt21(self, C: int) -> int:
        if C == 0: return 0
        def f(x):
            return x * x - C
        def f_derivative(x):
            return 2 * x
        x = C
        while True:
            xt = x - f(x)/f_derivative(x)
            if abs(x - xt) < epsilon:
                return int(x)
            x = xt

    # 暴力的二分优化
    def mySqrt3(self, C: int) -> int:
        l,r = 0, C
        res = 0
        while l <= r:
            x = l + r >> 1
            if x * x <= C:
                res = x
                l = x + 1
            else:
                r = x - 1
        return int(res)

print(-2.384185791015625e-07)
x= 2147395599
print(Solution().mySqrt2(x))